# nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。 
# 
#  给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。 
# 
#  对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 
# nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。 
# 
#  返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。 
# 
#  
# 
#  示例 1： 
# 
#  
# 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
# 输出：[-1,3,-1]
# 解释：nums1 中每个值的下一个更大元素如下所述：
# - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
# - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
# - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。 
# 
#  示例 2： 
# 
#  
# 输入：nums1 = [2,4], nums2 = [1,2,3,4].
# 输出：[3,-1]
# 解释：nums1 中每个值的下一个更大元素如下所述：
# - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
# - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
#  
# 
#  
# 
#  提示： 
# 
#  
#  1 <= nums1.length <= nums2.length <= 1000 
#  0 <= nums1[i], nums2[i] <= 10⁴ 
#  nums1和nums2中所有整数 互不相同 
#  nums1 中的所有整数同样出现在 nums2 中 
#  
# 
#  
# 
#  进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？ 
# 
#  Related Topics 栈 数组 哈希表 单调栈 👍 1228 👎 0
from typing import List


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
        """
        思路一：暴力法
        :param nums1:
        :param nums2:
        :return:

        d = {}
        res = []
        for i in range(len(nums2)):
            for j in range(i + 1, len(nums2)):
                if nums2[j] > nums2[i]:
                    d[nums2[i]] = nums2[j]
                    break

        for n in nums1:
            if n in d:
                res.append(d[n])
            else:
                res.append(-1)
        return res
        """
        """
        思路二：
        单调栈：单调栈是一种特殊的栈，栈中的元素保持单调递增或递减的顺序。在这个问题中，我们可以使用单调递减栈来找到 nums2 中每个元素的下一个更大元素。
        哈希表：哈希表用于存储 nums2 中每个元素的下一个更大元素。这样，当我们遍历 nums1 时，可以直接从哈希表中查找结果。
        算法步骤：遍历 nums2，使用单调栈找到每个元素的下一个更大元素，并将结果存储在哈希表中。遍历 nums1，从哈希表中查找每个元素的下一个更大元素。
        """
        d = {}
        stcak = []
        res = []
        for i in range(len(nums2)):
            while stcak and nums2[i] > stcak[-1]:
                num = stcak.pop()
                d[num] = nums2[i]
            # 在找到栈顶元素的下一个最大元素后，更新栈顶元素
            stcak.append(nums2[i])
        if stcak:
            for num in stcak:
                d[num] = -1

        for n1 in nums1:
            res.append(d[n1])
        return res


# leetcode submit region end(Prohibit modification and deletion)
print(Solution().nextGreaterElement(nums1=[4, 1, 2], nums2=[1, 3, 4, 2]))
